"""
作业2：二分查找、递归和动态规划
"""


import time
from functools import wraps


# PEP8
# 终极原则: 高内聚 低耦合
# 面向对象: SOLID
# GoF 《设计模式》- 23种场景 - Python中有16种都被弱化了
# 单例 / 工厂 / 原型 / 代理 / 装饰器 / 代理
def clock(func):

    @wraps(func)
    def wrapper(*args, **kwargs):
        if kwargs['level'] == 0:
            start = time.perf_counter()
        result = func(*args, **kwargs)
        if kwargs['level'] == 0:
            end = time.perf_counter()
            print(f'Execution time: {end - start}s')
        return result

    return wrapper


# 动态规划 - 问题的解有最优子结构
# Fibonacci
@clock
def fib(n, temp={}, *, level):
    if n == 1 or n == 2:
        return 1
    try:
        return temp[n]
    except KeyError:
        level += 1
        temp[n] = fib(n - 1, level=level) + fib(n - 2, level=level)
        return temp[n]


# stackoverflow.com
def f(n, result=1):
    # 收敛条件(什么时候就不要在递归了)
    if n == 0 or n == 1:
        return result
    # 递归公式
    return f(n - 1, n * result)


# 注意1：能用循环写的代码一定不要使用递归
# 注意2：如果用递归也尽量使用尾递归(只需要递归不需要回溯)
# 练习3：请大家将下面的递归代码修改为尾递归
def my_sum(n):
    if n == 1:
        return 1
    return n + my_sum(n - 1)


# 练习2: 如果列表元素不支持>和<这两个运算符
# 请仿照之前的方式通过传入实现元素比较的函数
# 练习5：请尝试用递归书写下面的代码
def search(alist, key, comp=None) -> int:
    low, high = 0, len(alist) - 1
    while low <= high:
        mid = (low + high) // 2
        if key > alist[mid]:
            low = mid + 1
        elif key < alist[mid]:
            high = mid - 1
        else:
            return mid
    return -1


# 小孩爬楼梯 1, 2, 3
# 10个台阶 - 有多少种走法
# 练习4：用动态规划优化下面的代码
def walk(steps):
    if steps < 0:
        return 0
    elif steps == 0:
        return 1
    return walk(steps - 1) + walk(steps - 2) + walk(steps - 3)


def main():
    # 如果刚才的递归没有经过优化
    # 那么计算第120个Fibonacci数在我这台计算机上大约需要20万年
    # 因为计算的复杂度呈现几何级数增长
    for n in range(1, 121):
        print(n, fib(n, level=0))
        print('-' * 39)
        """
        # 下面的方式可以调用装饰器之前的函数
        print(n, fib.__wrapped__(n, level=0))
        """
    print('小孩爬楼梯'.center(21, '-'))
    for steps in range(1, 11):
        total = walk(steps)
        print(f'{steps}'.rjust(8), '---->', f'{total}'.ljust(8))
    # 当发生函数调用时 需要做保存现场和恢复现场的工作
    # 保存现场和恢复现场的工作都是利用栈(stack)来实现的
    # 栈是一个FILO的结构 - 栈非常的快但是它很小
    import sys
    sys.setrecursionlimit(99999)
    # 用递归求20的阶乘
    print(f(20))
    # 用递归做1-1000求和
    print(my_sum(1000))
    # 二分查找/折半查找)
    list1 = [12, 35, 46, 57, 66, 78, 81, 90]
    print(search(list1, 35))
    print(search(list1, 80))
    print(search(list1, 81))


if __name__ == '__main__':
    main()
